package com.yanceysong.codetop.s11_s20;

import com.yanceysong.common.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName S12_Mid_102_二叉树的层序遍历
 * @Description LeetCode 102 - 二叉树的层序遍历
 * @date 2025/8/27 16:54
 * @Author yanceysong
 * @Version 1.0
 */
public class S12_Mid_102_二叉树的层序遍历 {
    /**
     * LeetCode链接
     * <a href="https://leetcode.cn/problems/binary-tree-level-order-traversal/description/">...</a>
     * <p>
     * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     * <p>
     * 示例1：
     * .      3
     * .    / \
     * .   9   20
     * .      /  \
     * .      15   7
     * 输入：root = [3,9,20,null,null,15,7]
     * 输出：[[3],[9,20],[15,7]]
     * <p>
     * 示例2：
     * 输入：root = [1]
     * 输出：[[1]]
     * <p>
     * 示例3：
     * 输入：root = []
     * 输出：[]
     * <p>
     * 提示：
     * 树中节点数目在范围 [0, 2000] 内
     * -1000 <= Node.val <= 1000
     * <p>
     * 解题：
     * {@link com.yanceysong.codetop.s11_s20.S12_Mid_102_二叉树的层序遍历#levelOrder(com.yanceysong.common.TreeNode)}
     * <p>
     * ==================== 二叉树层次遍历算法图解 ====================
     * <p>
     * 算法思路：广度优先搜索（BFS）+ 队列
     * 1. 使用队列存储每一层的节点
     * 2. 逐层处理，每次处理完一层再处理下一层
     * 3. 记录每一层的节点值到结果列表中
     * 4. 将当前层节点的子节点加入队列，准备下一层遍历
     * <p>
     * 执行示例：
     * .     3
     * .   /  \
     * .  9     20
     * . / \   / \
     * .     15   7
     * <p>
     * 层次遍历过程详解：
     * <p>
     * 初始状态：
     * 队列: [3]
     * 结果: []
     * <p>
     * 第1层处理：
     * 当前层大小: 1
     * 队列状态: [3]
     * 处理节点3: 值=3, 左子节点=9, 右子节点=20
     * 当前层结果: [3]
     * 子节点入队: [9, 20]
     * 结果更新: [[3]]
     * <p>
     * 第2层处理：
     * 当前层大小: 2
     * 队列状态: [9, 20]
     * 处理节点9: 值=9, 左子节点=null, 右子节点=null
     * 处理节点20: 值=20, 左子节点=15, 右子节点=7
     * 当前层结果: [9, 20]
     * 子节点入队: [15, 7]
     * 结果更新: [[3], [9, 20]]
     * <p>
     * 第3层处理：
     * 当前层大小: 2
     * 队列状态: [15, 7]
     * 处理节点15: 值=15, 左子节点=null, 右子节点=null
     * 处理节点7: 值=7, 左子节点=null, 右子节点=null
     * 当前层结果: [15, 7]
     * 子节点入队: []
     * 结果更新: [[3], [9, 20], [15, 7]]
     * <p>
     * 最终结果：[[3], [9, 20], [15, 7]]
     * <p>
     * ==================== 队列操作详解 ====================
     * <p>
     * 关键技巧：层次分离
     * 问题：如何区分不同层的节点？
     * 解决：在处理每一层之前，先记录当前队列的大小
     * <p>
     * 队列大小的意义：
     * - 队列大小 = 当前层的节点数量
     * - 通过for循环精确控制每层处理的节点数
     * - 避免不同层节点混合处理
     * <p>
     * 处理流程：
     * 1. 记录当前队列大小size（当前层节点数）
     * 2. 循环size次，处理当前层的所有节点
     * 3. 每处理一个节点，将其子节点加入队列（下一层）
     * 4. 当前层处理完毕，队列中只剩下下一层的节点
     * <p>
     * 时间复杂度：O(n)，每个节点访问一次
     * 空间复杂度：O(w)，w为二叉树的最大宽度（最多一层的节点数）
     * <p>
     * 算法优势：
     * 1. 自然的层次分离，无需额外标记
     * 2. 一次遍历完成，效率高
     * 3. 代码简洁，易于理解和实现
     * <p>
     * ================================================================
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 边界检查：空树直接返回空列表
        if (root == null) {
            return new ArrayList<>();
        }

        // 初始化结果列表和队列
        List<List<Integer>> result = new ArrayList<>();           // 存储最终结果
        LinkedList<TreeNode> queue = new LinkedList<>();          // BFS遍历队列

        // 步骤1：将根节点加入队列，开始BFS遍历
        queue.add(root);

        // 步骤2：BFS主循环 - 当队列不为空时继续处理
        while (!queue.isEmpty()) {
            // 步骤3：记录当前层的节点数量（关键技巧）
            // 此时队列中的所有节点都属于同一层
            int currentLevelSize = queue.size();

            // 步骤4：创建当前层的结果列表
            List<Integer> currentLevelValues = new ArrayList<>();

            // 步骤5：处理当前层的所有节点
            for (int i = 0; i < currentLevelSize; i++) {
                // 从队列头部取出当前层的节点
                TreeNode currentNode = queue.removeFirst();

                // 将当前节点的值加入当前层结果
                currentLevelValues.add(currentNode.val);

                // 步骤6：将当前节点的子节点加入队列（下一层）
                // 注意：按照从左到右的顺序加入
                if (currentNode.left != null) {
                    queue.addLast(currentNode.left);      // 左子节点先入队
                }
                if (currentNode.right != null) {
                    queue.addLast(currentNode.right);     // 右子节点后入队
                }
            }

            // 步骤7：将当前层的结果加入最终结果列表
            result.add(currentLevelValues);
        }

        // 返回层次遍历结果
        return result;
    }

    public static void main(String[] args) {
        S12_Mid_102_二叉树的层序遍历 solution = new S12_Mid_102_二叉树的层序遍历();

        System.out.println("=== 二叉树层次遍历测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 不同树结构测试
        System.out.println("\n--- 测试3: 不同树结构测试 ---");
        testDifferentTreeStructures(solution);

        // 测试4: 特殊情况测试
        System.out.println("\n--- 测试4: 特殊情况测试 ---");
        testSpecialCases(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        // 测试6: 复杂树结构测试
        System.out.println("\n--- 测试6: 复杂树结构测试 ---");
        testComplexTreeStructures(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S12_Mid_102_二叉树的层序遍历 solution) {
        // 示例1: [3,9,20,null,null,15,7] -> [[3],[9,20],[15,7]]
        TreeNode root1 = createTree(new Integer[]{3, 9, 20, null, null, 15, 7});
        List<List<Integer>> expected1 = List.of(
                List.of(3),
                List.of(9, 20),
                List.of(15, 7)
        );
        testLevelOrder(solution, root1, expected1, "题目示例1");

        // 示例2: [1] -> [[1]]
        TreeNode root2 = createTree(new Integer[]{1});
        List<List<Integer>> expected2 = List.of(List.of(1));
        testLevelOrder(solution, root2, expected2, "题目示例2(单节点)");

        // 示例3: [] -> []
        TreeNode root3 = null;
        List<List<Integer>> expected3 = List.of();
        testLevelOrder(solution, root3, expected3, "题目示例3(空树)");

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCases(S12_Mid_102_二叉树的层序遍历 solution) {
        // 测试1: null输入
        List<List<Integer>> result1 = solution.levelOrder(null);
        System.out.println("null输入: null -> " + result1 + " (期望: [])");
        assert result1.isEmpty() : "null输入测试失败";

        // 测试2: 单节点树
        TreeNode root2 = new TreeNode(42);
        List<List<Integer>> expected2 = List.of(List.of(42));
        testLevelOrder(solution, root2, expected2, "单节点树");

        // 测试3: 只有左子树
        TreeNode root3 = createTree(new Integer[]{1, 2, null, 3, null});
        List<List<Integer>> expected3 = List.of(
                List.of(1),
                List.of(2),
                List.of(3)
        );
        testLevelOrder(solution, root3, expected3, "只有左子树");

        // 测试4: 只有右子树
        TreeNode root4 = createTree(new Integer[]{1, null, 2, null, 3});
        List<List<Integer>> expected4 = List.of(
                List.of(1),
                List.of(2),
                List.of(3)
        );
        testLevelOrder(solution, root4, expected4, "只有右子树");

        // 测试5: 两层完全二叉树
        TreeNode root5 = createTree(new Integer[]{1, 2, 3});
        List<List<Integer>> expected5 = List.of(
                List.of(1),
                List.of(2, 3)
        );
        testLevelOrder(solution, root5, expected5, "两层完全二叉树");

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 测试不同树结构
     */
    private static void testDifferentTreeStructures(S12_Mid_102_二叉树的层序遍历 solution) {
        // 测试1: 完全二叉树
        TreeNode root1 = createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});
        List<List<Integer>> expected1 = List.of(
                List.of(1),
                List.of(2, 3),
                List.of(4, 5, 6, 7)
        );
        testLevelOrder(solution, root1, expected1, "完全二叉树");

        // 测试2: 满二叉树
        TreeNode root2 = createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15});
        List<List<Integer>> expected2 = List.of(
                List.of(1),
                List.of(2, 3),
                List.of(4, 5, 6, 7),
                List.of(8, 9, 10, 11, 12, 13, 14, 15)
        );
        testLevelOrder(solution, root2, expected2, "满二叉树");

        // 测试3: 左偏树
        TreeNode root3 = createTree(new Integer[]{1, 2, null, 3, null, null, null, 4});
        List<List<Integer>> expected3 = List.of(
                List.of(1),
                List.of(2),
                List.of(3),
                List.of(4)
        );
        testLevelOrder(solution, root3, expected3, "左偏树");

        // 测试4: 右偏树
        TreeNode root4 = createTree(new Integer[]{1, null, 2, null, null, null, 3, null, null, null, null, null, null, null, 4});
        List<List<Integer>> expected4 = List.of(
                List.of(1),
                List.of(2),
                List.of(3),
                List.of(4)
        );
        testLevelOrder(solution, root4, expected4, "右偏树");

        // 测试5: 不平衡树
        TreeNode root5 = createTree(new Integer[]{1, 2, 3, 4, null, null, 5, 6, 7, null, null, null, null, null, 8});
        List<List<Integer>> expected5 = List.of(
                List.of(1),
                List.of(2, 3),
                List.of(4, 5),
                List.of(6, 7, 8)
        );
        testLevelOrder(solution, root5, expected5, "不平衡树");

        System.out.println("✓ 不同树结构测试通过");
    }

    /**
     * 测试特殊情况
     */
    private static void testSpecialCases(S12_Mid_102_二叉树的层序遍历 solution) {
        // 测试1: 包含负数的树
        TreeNode root1 = createTree(new Integer[]{-1, -2, -3, -4, -5});
        List<List<Integer>> expected1 = List.of(
                List.of(-1),
                List.of(-2, -3),
                List.of(-4, -5)
        );
        testLevelOrder(solution, root1, expected1, "包含负数");

        // 测试2: 包含零的树
        TreeNode root2 = createTree(new Integer[]{0, -1, 1, -2, 0, 0, 2});
        List<List<Integer>> expected2 = List.of(
                List.of(0),
                List.of(-1, 1),
                List.of(-2, 0, 0, 2)
        );
        testLevelOrder(solution, root2, expected2, "包含零");

        // 测试3: 相同值的树
        TreeNode root3 = createTree(new Integer[]{5, 5, 5, 5, 5, 5, 5});
        List<List<Integer>> expected3 = List.of(
                List.of(5),
                List.of(5, 5),
                List.of(5, 5, 5, 5)
        );
        testLevelOrder(solution, root3, expected3, "相同值");

        // 测试4: 大数值
        TreeNode root4 = createTree(new Integer[]{1000, -1000, 999, -999});
        List<List<Integer>> expected4 = List.of(
                List.of(1000),
                List.of(-1000, 999),
                List.of(-999)
        );
        testLevelOrder(solution, root4, expected4, "大数值");

        // 测试5: 稀疏树（很多null节点）
        TreeNode root5 = createTree(new Integer[]{1, null, 2, null, null, null, 3, null, null, null, null, null, null, null, 4});
        List<List<Integer>> expected5 = List.of(
                List.of(1),
                List.of(2),
                List.of(3),
                List.of(4)
        );
        testLevelOrder(solution, root5, expected5, "稀疏树");

        System.out.println("✓ 特殊情况测试通过");
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S12_Mid_102_二叉树的层序遍历 solution) {
        // 测试1: 中等规模完全二叉树
        System.out.println("性能测试1: 7层完全二叉树(127个节点)");
        testPerformanceCase(solution, 7);

        // 测试2: 较大规模完全二叉树
        System.out.println("性能测试2: 10层完全二叉树(1023个节点)");
        testPerformanceCase(solution, 10);

        // 测试3: 大规模完全二叉树
        System.out.println("性能测试3: 12层完全二叉树(4095个节点)");
        testPerformanceCase(solution, 12);

        System.out.println("✓ 性能测试通过");
    }

    /**
     * 辅助方法：性能测试用例
     */
    private static void testPerformanceCase(S12_Mid_102_二叉树的层序遍历 solution, int levels) {
        // 创建完全二叉树
        TreeNode root = createCompleteBinaryTree(levels);

        long startTime = System.currentTimeMillis();
        List<List<Integer>> result = solution.levelOrder(root);
        long endTime = System.currentTimeMillis();

        // 验证结果
        assert result != null : "性能测试：结果不应为空";
        assert result.size() == levels : "性能测试：层数不正确";

        // 验证每层节点数
        for (int i = 0; i < levels; i++) {
            int expectedNodesInLevel = (int) Math.pow(2, i);
            if (i == levels - 1) {
                // 最后一层可能不满
                assert result.get(i).size() <= expectedNodesInLevel : "性能测试：第" + (i + 1) + "层节点数过多";
            } else {
                assert result.get(i).size() == expectedNodesInLevel : "性能测试：第" + (i + 1) + "层节点数不正确";
            }
        }

        int totalNodes = (int) Math.pow(2, levels) - 1;
        System.out.println("  层数: " + levels +
                           ", 总节点数: " + totalNodes +
                           ", 执行时间: " + (endTime - startTime) + "ms");

        // 验证时间复杂度合理
        assert (endTime - startTime) < 1000 : "性能测试：执行时间过长，可能存在性能问题";
    }

    /**
     * 测试复杂树结构
     */
    private static void testComplexTreeStructures(S12_Mid_102_二叉树的层序遍历 solution) {
        // 测试1: 锯齿状树
        TreeNode root1 = createTree(new Integer[]{1, 2, null, 3, null, null, null, 4, null, null, null, null, null, null, null, 5});
        List<List<Integer>> expected1 = List.of(
                List.of(1),
                List.of(2),
                List.of(3),
                List.of(4),
                List.of(5)
        );
        testLevelOrder(solution, root1, expected1, "锯齿状树");

        // 测试2: 混合结构树
        TreeNode root2 = createTree(new Integer[]{1, 2, 3, 4, null, 6, 7, 8, 9, null, null, null, 13, 14, 15});
        List<List<Integer>> expected2 = List.of(
                List.of(1),
                List.of(2, 3),
                List.of(4, 6, 7),
                List.of(8, 9, 13, 14, 15)
        );
        testLevelOrder(solution, root2, expected2, "混合结构树");

        // 测试3: 深度不均匀的树
        TreeNode root3 = createTree(new Integer[]{1, 2, 3, 4, 5, null, null, 6, null, 7, 8});
        List<List<Integer>> expected3 = List.of(
                List.of(1),
                List.of(2, 3),
                List.of(4, 5),
                List.of(6, 7, 8)
        );
        testLevelOrder(solution, root3, expected3, "深度不均匀");

        System.out.println("✓ 复杂树结构测试通过");
    }

    /**
     * 创建二叉树的辅助方法（从数组创建）
     */
    private static TreeNode createTree(Integer[] values) {
        if (values == null || values.length == 0 || values[0] == null) {
            return null;
        }

        TreeNode root = new TreeNode(values[0]);
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int index = 1;
        while (!queue.isEmpty() && index < values.length) {
            TreeNode current = queue.poll();

            // 处理左子节点
            if (values[index] != null) {
                current.left = new TreeNode(values[index]);
                queue.add(current.left);
            }
            index++;

            // 处理右子节点
            if (index < values.length && values[index] != null) {
                current.right = new TreeNode(values[index]);
                queue.add(current.right);
            }
            index++;
        }

        return root;
    }

    /**
     * 创建完全二叉树的辅助方法
     */
    private static TreeNode createCompleteBinaryTree(int levels) {
        if (levels <= 0) return null;

        TreeNode root = new TreeNode(1);
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int nodeValue = 2;
        int currentLevel = 1;

        while (currentLevel < levels && !queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode current = queue.poll();
                if (current == null) continue;

                // 添加左子节点
                current.left = new TreeNode(nodeValue++);
                queue.add(current.left);

                // 添加右子节点
                current.right = new TreeNode(nodeValue++);
                queue.add(current.right);
            }
            currentLevel++;
        }

        return root;
    }

    /**
     * 测试层次遍历的辅助方法
     */
    private static void testLevelOrder(S12_Mid_102_二叉树的层序遍历 solution, TreeNode root, List<List<Integer>> expected, String description) {
        List<List<Integer>> actual = solution.levelOrder(root);

        System.out.print(description + " - 输入: ");
        printTree(root);
        System.out.print(" -> 输出: " + actual);
        System.out.println(" (期望: " + expected + ")");

        assert actual.equals(expected) : description + "测试失败";
    }

    /**
     * 打印树结构的辅助方法（简化显示）
     */
    private static void printTree(TreeNode root) {
        if (root == null) {
            System.out.print("null");
            return;
        }

        List<List<Integer>> levels = new S12_Mid_102_二叉树的层序遍历().levelOrder(root);
        System.out.print("[");
        for (int i = 0; i < levels.size(); i++) {
            if (i > 0) System.out.print(",");
            System.out.print(levels.get(i));
        }
        System.out.print("]");
    }
}
